#include<string>
#include<vector>
#include<array>
#include<unordered_map>
#include<algorithm>
#include<limits>
#include <stack>
#include<iostream>
#include<sstream>
#include<deque>
#include<queue>
#include<set>
#define MOD 1000000007

struct poll
{
    int x;
    int y;
    int d;
    bool operator<(const poll &other) const
    {
        return d > other.d;
    }
    poll(int x, int y, int d) : x(x), y(y), d(d) {}
 
};
class Solution {
public:
    int trapRainWater(std::vector<std::vector<int>>& heightMap) {
std::priority_queue<poll> q;
        std::vector<int> move = {-1,0,1,0,-1};
        int n = heightMap.size();
        int m = heightMap[0].size();
        std::vector<std::vector<bool>> vistied (n,std::vector<bool> (m,false));
        for (int i=0;i<n;i++)
        {
            for (int j=0;j<m;j++)
            {
                if (i==0||j==0||i==n-1||j==m-1)
                {
                    q.emplace(i,j,heightMap[i][j]);
                    vistied[i][j]=true;
                }
            }
        }
int ans = 0;
        while(!q.empty())
        {
            poll p = q.top();
            q.pop();
            ans += p.d-heightMap[p.x][p.y];
            for (int i = 0;i<4;i++)
            {
                int x = p.x + move[i];
                int y = p.y + move[i+1];
                if (x<0||x>=n||y<0||y>=m||vistied[x][y])
                    continue;
                q.emplace(x,y,std::max(heightMap[x][y],p.d));
                vistied[x][y]=true;
            }
        }
        return ans;
    }
};